#include<iostream>
#include<vector>
#include"BalanceTree.h"
#include<cstdlib>
#include<algorithm>
#include<ctime>

using namespace std;

template <typename T>
void Avl_sort(vector<T> &_a)
{
    AvlTree<T> h;
    for(int i=0;i<_a.size();i++)
    {
	h.insert(_a[i]);
    }
    _a.clear();
    
    while(h.isEmpty()!=true)
    {
	_a.push_back(h.findMin());
	h.remove(h.findMin());
	
    }
}

template<typename T>
void Splay_sort(vector<T> &_a)
{
    SplayTree<T> t;
    for(int i=0;i<_a.size();i++)
    {
	t.insert(_a[i]);
    }
     _a.clear();
    
    while(t.isEmpty()!=true)
    {
	_a.push_back(t.findMin());
	t.remove(t.findMin());
	
    }
}

int main()
{
//生成随机数的数组大小为n,取值范围在100以内。

    int n;
    n=100;
    vector<int> a(n);

    for(int i=0;i<n;i++)
    {
	a[i]=i;
    }
    random_shuffle(a.begin(),a.end());
    cout<<"the vector before sorting is:";
     for(int i=0;i<n;i++)
     {
	cout<<a[i]<<' ';
      }
     cout<<endl;
    
    //再生成两个一样数组用于排序;
    vector<int> b;
    vector<int> c;
    c=a;
    b=a;
    clock_t startTime1,endTime1;
    //对b利用平衡树进行排序然后输出排序之后的结果并且记录排序的时间
     cout<<"the result of Avl_sort is:";
    startTime1 = clock();
    Avl_sort(b);
    endTime1 = clock(); 
     for(int i=0;i<n;i++)
	  {
	cout<<b[i]<<' ';
	 }
     cout<<endl;
    //输出排序过程中Avltree排序所需要的时间
    cout<<"the time used by Avl_sort is:";
    cout<<(double)(endTime1-startTime1) / CLOCKS_PER_SEC<<'s'<<endl;

    clock_t startTime2,endTime2;
    //对b利用splay树进行排序然后输出排序之后的结果并且记录排序的时间
     cout<<"the result of Splay_sort is:";
    startTime2 = clock();
    Splay_sort(c);
    endTime2 = clock(); 
     for(int i=0;i<n;i++)
    {
	cout<<c[i]<<' ';
      }
     cout<<endl;
     //输出排序过程中Splaytree排序所需要的时间
    cout<<"the time used by Splay_sort is:";
    cout<<(double)(endTime2-startTime2) / CLOCKS_PER_SEC<<'s'<<endl;
    
    
    

    





    return 0;


    
}
